Typical integrated circuit design environments make use of libraries of pre-designed standard cells (a cell library) which usually consist of from 500 cells to more than 1,000 cells. These libraries are composed of a number of simple, generic and standard logic functions that have been implemented in a form suitable for manufacturing. Each standard cell is a representation, typically the mask level representation, of the circuit that performs the logic function for that cell.
The logic functions performed by the cells in a typical cell library are intentionally general purpose and basic and represent common, low-level logic functions such as AND, OR, XOR, AND-OR-INVERT (AOI), Multiplexer, Adder, etc. These are functions are representative of patterns that are recognized by logic designers, and those that are used as the building blocks for manual logic design. Full custom logic design at the transistor level can sometimes include complex AOI functions that are identifiable from their logic description such as:(ā+ b)(c+d)
But such functions are typically not included in standard cell libraries, and not representative of specific basic building blocks that are known to logic designers. Instead, they are more likely to be custom designed at the transistor level as an AOI gate.
A portion of a typical integrated circuit (IC) design flow 100 is shown in FIG. 1. In the figure, an IC design is first shown as being present in step 110, which is then translated to logic gates in step 120. In most cases this translation is performed by an automatic logic synthesis tool to derive a netlist based on a set of the aforementioned generic logic functions. This translation is often necessary as there are many different methods in common use for design specification. Those methods may include specification using a high-level programming language such as Verilog, VHDL or C or by manually entering schematics using a computer-aided design system.
As a high level language cannot be directly implemented into the physical layout of an integrated circuit, it is first converted to a gate level implementation. The result of a conversion step 130 is a representation of the design called a gate level netlist. This representation is usually in the form of simple logic functions such as NAND, NOR, etc. along with a representation of the connections between functions (the netlist).
Automatic logic synthesis tools are then generally used, as shown at library binding step 140, to bind a design to an implementation, based on a set of manufacturing technology specific logic cells from a cell library 150. The synthesis tool selects cells from the library 150 based on a set of implementation goals that may include any combination of metrics related to area, performance or power and possibly manufacturing yield, to obtain a cell-based netlist 160.
Within the context of the conventional design flow as described above, techniques for optimization using regularity extraction have been proposed for designs dominated by datapaths, which are formed by a small number of repeating logic elements (or bit slices) that are interconnected in a very organized pattern, and other regular circuit structures including RAMs, PLAs, array multipliers etc. For such designs, identifying repeating regularity in circuits simplifies the effort required via synthesis, optimization and layout. However, such regularity extraction techniques rely on the assumption that the designs inherently have within them a high degree of regularity. For example, most of these techniques use information such as bus names and datapath features such as high-fanout control nets to identify repeating strictures, such as bit slices. These techniques do not apply, therefore, to more general design flows and logic descriptions that are without such organization and repetition. Also, these techniques to identify repeating regularity do not modify the underlying structural or functional topology of the circuit, which further makes them ineffective for generalized logic and random logic applications.